package _11_整理题目._4_动态规划._打家劫舍;

import org.junit.Test;

import java.util.Arrays;

/**
 * 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，
 * 影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，
 * 如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
 *
 * 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，
 * 一夜之内能够偷窃到的最高金额。
 *
 * 输入：[2,7,9,3,1]
 * 输出：12
 * 解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，
 * 接着偷窃 5 号房屋 (金额 = 1)。
 *     偷窃到的最高金额 = 2 + 9 + 1 = 12 。
 *
 * 动态规划一  时间 O(n)，空间 O(n)
 * 定义 dp[i]： 表示前 i 个房间能偷到的最高金额
 * 初始条件：只有一个房间，只有两个房间
 * 转移方程：不能偷相邻的，所以 dp[i] = Math.max(dp[i-1], dp[i-2]+nums[i])
 *                                          偷前面一家，偷当前的这家
 * 动态规划二 时间 O(n)，空间 O(1)
 * 使用滚动数组优化，记录 dp[i-1] dp[i-2]
 *
 * 递归
 *
 *
 */
public class _01_打家劫舍_1 {

    public int rob1(int[] nums) {
        int n = nums.length;
        if (n == 1) return nums[0];
        int[] dp = new int[n];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < n; i++) {
            dp[i] = Math.max(dp[i-1], dp[i-2]+nums[i]);
        }
        return dp[n-1];
    }

    public int rob2(int[] nums) {
        int n = nums.length;
        if (n == 1) return nums[0];
        int a = nums[0];
        int b = Math.max(nums[0], nums[1]);
        int c = b;
        for (int i = 2; i < n; i++) {
            c = Math.max(b, a+nums[i]);
            a = b;
            b = c;
        }
        return c;
    }

    public int rob3(int[] nums) {
        int n = nums.length;
        return dfs(nums, n-1);
    }
    private int dfs(int[] nums, int n) {
        if(n == 0) return nums[0];
        if(n == 1) return Math.max(nums[0], nums[1]);
        return Math.max(dfs(nums, n-1), dfs(nums, n-2)+nums[n]);
    }

    public int rob4(int[] nums) {
        int n = nums.length;
        int[] mem = new int[n];
        Arrays.fill(mem, -1);
        return dfs1(nums, mem, n-1);
    }
    private int dfs1(int[] nums, int[] mem, int n) {
        if (n == 0) return nums[0];
        if (n == 1) return Math.max(nums[0], nums[1]);
        if (mem[n] == -1) {
            mem[n] = Math.max(dfs1(nums, mem, n-1), dfs1(nums, mem, n-2)+nums[n]);
        }
        return mem[n];
    }

    @Test
    public void main() {
        int[] nums = {2,7,9,3,1};
        System.out.println(rob1(nums));
        System.out.println(rob2(nums));
    }

}
